package dp;

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

public class P313 {
    public int nthSuperUglyNumber(int n, int[] primes) {
        Set<Long> seen = new HashSet<Long>();
        PriorityQueue<Long> heap = new PriorityQueue<Long>();
        seen.add(1L);
        heap.offer(1L);
        int ugly = 0;
        for (int i = 0; i < n; i++) {
            long curr = heap.poll();
            ugly = (int) curr;
            for (int prime : primes) {
                long next = curr * prime;
                if (seen.add(next)) {
                    heap.offer(next);
                }
            }
        }
        return ugly;
    }

    public int dp(int n, int[] primes) {
        Set<Integer> uniqueSet = new HashSet<>();
        int[] dp = new int[n];
        dp[0] = 1;
        // 指向当前数的指针
        int[] pointers = new int[primes.length];
        uniqueSet.add(1);

        for (int i = 1; i < n; i++) {
            int minIdx = -1, total = Integer.MAX_VALUE;
            for (int j = 0; j < pointers.length; j++) {
                int now = dp[pointers[j]] * primes[j];
                if (now < total && !uniqueSet.contains(now)) {
                    total = now;
                    minIdx = j;
                } else if (uniqueSet.contains(now)) {
                    pointers[j]++;
                    j--;
                }
            }
            pointers[minIdx]++;
            dp[i] = total;
            uniqueSet.add(total);
        }
        return dp[n - 1];
    }

    public static void main(String[] args) {
        int result = new P313().dp(45, new int[]{2, 3, 7, 13, 17, 23, 31, 41, 43, 47});
        System.out.println(result);
    }

}
